package com.example.lib5.sort.test;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        //数组
        int arr[]={8,4,5,7,1,3,6,2};
        int temp[]=new int[arr.length];//归并排序需要一个额外的空间
//        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSortC(int[] arr,int left,int right,int[] temp){
        //判断是否要继续遍历
        if (left<right){
            //获取中间值
            int center=(left+right)/2;
            //左右分
            mergeSortC(arr,left,center,temp);
            mergeSortC(arr,center+1,right,temp);
            //合并
            mergeC(arr,left,center,right,temp);
        }


    }
    public static void mergeC(int [] arr,int left,int mid,int right,int[] temp){
        //初始化一些值
        int i=left;
        int j=mid+1;
        int indexTemp=0;
        //遍历数组，加入到arr
        while (i<=mid&&j<=right){
            if (arr[i]<=arr[j]){
                temp[indexTemp]=arr[i];
                i++;
                indexTemp++;
            }else {
                temp[indexTemp]=arr[j];
                j++;
                indexTemp++;
            }

        }
        //剩余的加入到arr
        while (i<=mid) {
            temp[indexTemp]=arr[i];
            indexTemp++;
            i++;
        }
        while (j<=right) {
            temp[indexTemp]=arr[j];
            indexTemp++;
            j++;
        }
        //返回arr
        indexTemp=0;
        int arrIndex=left;
        if (arrIndex<=right) {
            arr[arrIndex]=temp[indexTemp];
            indexTemp++;
            arrIndex++;
        }
    }



}
